package com.springboot.prac.prac03_algorithm.list;


/**
 * 链表 新增/删除/获取
 */
public class OperateList {
    // 头结点
    private Node head;
    // 尾节点
    private Node last;
    // 链表长度
    private int size;

    public void insert(int data, int index) {
        // 链表节点插入前，先判断index
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }

        Node insertNode = new Node(data);

        // 空链表
        if (size == 0) {
            head = insertNode;
            last = insertNode;
        } else if (index == 0) {
            insertNode.next = head;
            head = insertNode;
        } else if (index == size) {
            last.next = insertNode;
            last = insertNode;
        } else {
            Node preNode = get(index - 1);
            insertNode.next = preNode.next;
            preNode.next = insertNode;
        }

        size++;
    }

    public Node remove(int index) throws Exception {
        // 链表节点删除前，先判断index
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }

        Node removeNode = get(index);

        // 空链表
        if (size == 0) {
            throw new Exception("链表为空");
        } else if (index == 0) {
            head = removeNode.next;
        } else if (index == size) {
            Node preNode = get(index - 1);
            preNode.next = null;
        } else {
            Node preNode = get(index - 1);
            preNode.next = removeNode.next;
        }

        size--;
        return removeNode;
    }

    public Node get(int index) {
        // 链表节点查询前，先判断index
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }

        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }

        return temp;
    }

    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public void output() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public static void main(String[] args) throws Exception {
        OperateList operateList = new OperateList();
        operateList.insert(3,0);
        operateList.insert(7,1);
        operateList.insert(9,2);
        operateList.insert(5,3);
        operateList.insert(6,1);
        operateList.remove(0);
        operateList.output();
    }
}
